14 de julio de 2016

Objetivos

  • Estudiar la incertidumbre que presentan partidas de StarCraft, el clásico juego de estrategia en tiempo real.
  • Paso previo a la optimización con incertidumbre: vamos a estudiarla primero.
  • La incertidumbre es un factor "aleatorio", ya que está fuera de control.
  • El tiempo de partida es un factor clave. Aunque veremos que hay más factores importantes.

Partes del desarrollo

  • Matemáticas: Aprendizaje estadístico
  • Informática: R + MariaDB (SQL)

Matemáticas

Aprendizaje estadístico

  • Rama de las matemáticas que estudia el aprendizaje desde datos utlizando técnicas estadísticas.
  • Espacio de entrada \(\mathcal{X} \subset \mathbb{R}^d\)
  • Espacio de salida \(\mathcal{Y}\)
  • Función objetivo desconocida \(f:\mathcal{X} \rightarrow \mathcal{Y}\)
  • \(\{(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)\} \subset \mathcal{X} \times \mathcal{Y} \mid f(x_i) = y_i\)
  • Buscar una función \(g \in \mathcal{H} \mid g \approx f\)

Aprendizaje estadístico

  • Regresión: Se busca una relación entre la variable dependiente y la independiente.
  • Clasificación: Se busca una función que para una entrada, le asigne una etiqueta. En problemas binarios, esta etiqueta suele ser -1 o 1.
  • Estimación de densidad: Similar a clasificación, pero el objetivo no es dar una clase, sino la probabilidad de pertenecer a dicha clase.

Ejemplo

Ejemplo clasificado

\(g = \text{signo}(X2 - (5.8836615)X1 - (-2.366914))\)

Factibilidad del aprendizaje

  • \(E_{in}(h) = \frac{1}{N} \sum_{n=1}^N \chi(h(x_n) \neq f(x_n))\)
  • \(E_{out}(h) = \mathbb{P}[h(\textbf{x}) \neq f(\textbf{x})], \; \textbf{x} \in \mathcal{X}\)

  • \(E_{in}(g) \approx E_{out}(g)\)
  • \(E_{in}(g) \approx 0\)

Factibilidad del aprendizaje

Si \(X_1, X_2, \ldots, X_n\) son independientes y \(0 \leq X_i \leq 1 \; (i=1,2,\ldots,n)\), entonces para \(\epsilon>0\) y una función \(h\) se da:

\[\mathbb{P}\left[ | E_{in}(h) - E_{out}(h) | \geq \epsilon \right] \leq 2 e^{-2 n \epsilon^2}\]

Para una función binaria f, un conjunto de hipótesis \(\mathcal{H}\), cualquier algoritmo de aprendizaje \(\mathcal{A}\) y cualquier distribución de probabilidad P, se da:

\[E_{out}(g) \leq E_{in}(g) + \sqrt{\frac{8}{N} \ln \frac{4m_{\mathcal{H}}(2N)}{\delta}} ,\; \delta \ \text{nivel de tolerancia.}\]

Donde \(m_{\mathcal{H}}(N)\) está acotado por un polinomio de grado \(d_{VC}\).

Sobreajuste

Regularización

Ingeniería Informática

Datos disponibles

  • 6 bases de datos relacionales.
  • Más de 4000 partidas.

Distribución de la duración de partidas

Distribución de la duración < 75000

Componentes de una partida

Componentes de una partida

¿Reducir los datos?

  • Algunas características, como el Supply, los valores de unidades o edificios del jugador que pierde caen rápidamente en un determinado momento de la partida.
  • En general, el jugador que gana tiene sus gráficas por encima de las del jugador contrario.

Extracción de información

  • XGBoost: biblioteca que implementa Gradient Boosting de manera eficiente y con gran rendimiento. Regularización evita sobreajuste.
  • Boosting es un modelo de tipo ensemble (unión de clasificadores débiles).
  • Los detalles de la implementación se encuentran en (Chen and Guestrin (2016) ).

Resultados con recta de regresión

Resultados con área bajo la curva

Resultados con datos en crudo

Resultados con datos en crudo

Resultados con datos en crudo

Resultados con datos en crudo

Resultados con datos en crudo

Resultados con datos en crudo

Conclusiones

Conclusiones

  • La incertidumbre baja a lo largo de la partida
  • La elección de las características y del modelo han sido acertadas.

Trabajo futuro

  • Crear un bot competitivo utilizando características y un modelo de aprendizaje similares a los propuestos, mejorando la gestión de la incertidumbre que presentan bots anteriores, pudiendo adaptar mejor su estrategia o hacerlo en un momento anterior.
  • Combinar metaheurísticas y predicción del ganador para acelerar la ejecución de los algoritmos. Por ejemplo, dando una partida por resuelta mucho antes de que termine realmente.

Referencias

Abu-Mostafa, Yaser S., Malik Magdon-Ismail, and Hsuan-Tien Lin. 2012. Learning from Data. AMLBook.

Bishop, Christopher M. 2006. Pattern Recognition and Machine Learning (Information Science and Statistics). Secaucus, NJ, USA: Springer-Verlag New York, Inc.

Chen, Tianqi, and Carlos Guestrin. 2016. “XGBoost: A Scalable Tree Boosting System.” CoRR abs/1603.02754. http://arxiv.org/abs/1603.02754.

James, Gareth, Daniela Witten, Trevor Hastie, and Robert Tibshirani. 2014. An Introduction to Statistical Learning: With Applications in R. Springer Publishing Company, Incorporated.